﻿//#define _CRT_SECURE_NO_WARNINGS 1
//#include<stdio.h>
//#include<stdlib.h>
//#include <iostream>
//http://oj33.cn/contest.php?cid=1075
//https://blog.csdn.net/qq_37482202/article/details/89513877
//
//typedef struct
//{
//	int weight;
//	int left;
//	int right;
//	int parent;
//}Node, * HuffmanTree;
//
////存储哈夫曼编码
//typedef char* HuffmanCode;
//void CreateHuffmanTree(HuffmanTree* T, int w[], int n);
//void select(HuffmanTree* T, int n, int* m1, int* m2);
//void CreateHuffmanCode(HuffmanTree* T, HuffmanCode* C, int n);
///*创建哈夫曼树*/
////传入n个权重，作为哈夫曼树的n个叶子结点
//void CreateHuffmanTree(HuffmanTree* T, int w[], int n)
//{
//	int m = 2 * n - 1;//n个叶子结点，共m个结点
//	int m1, m2;//用于建立下一个结点的两结点，值为最小的两个
//	*T = (HuffmanTree)malloc((m + 1) * sizeof(Node));
//	//初始化前n个结点（叶子结点），权重赋值，暂时没有左右孩子与父亲
//	for (int i = 1; i <= n; i++)
//	{
//		(*T)[i].weight = w[i];
//		(*T)[i].left = (*T)[i].right = (*T)[i].parent = 0;
//		
//	}
//	//初始化[n+1,m]个结点(非叶子结点)
//	for (int i = n + 1; i <= m; i++)
//	{
//		(*T)[i].weight = (*T)[i].left = (*T)[i].right = (*T)[i].parent = 0;
//		
//	}
//
//	//开始建树，第i个结点的两孩子为m1,m2，权重为两孩子结点权重之和
//	for (int i = n + 1; i <= m; i++)
//	{
//		select(T, i - 1, &m1, &m2);
//		(*T)[i].left = m1;
//		(*T)[i].right = m2;
//		(*T)[m1].parent = i;
//		(*T)[m2].parent = i;
//		(*T)[i].weight = (*T)[m1].weight + (*T)[m2].weight;
//
//		/*printf("%d (%d %d)\n", (*T)[i].weight, (*T)[m1].weight, (*T)[m2].weight);*/
//	}
//	printf("\n");
//}
//
///*选取得到n个无父节点的两最小结点*/
//void select(HuffmanTree* T, int n, int* m1, int* m2)
//{
//	int m;//存储最小值的数组下标
//
//	//给m赋初值
//	for (int i = 1; i <= n; i++)
//	{
//		if ((*T)[i].parent == 0)
//		{
//			m = i;
//			break;
//		}
//	}
//	//找到当前最小的权重（叶子结点）
//	for (int i = 1; i <= n; i++)
//	{
//		if ((*T)[i].parent == 0 && (*T)[i].weight < (*T)[m].weight)
//		{
//			m = i;
//		}
//	}
//	//先赋给m1保存一个，再去寻找第二小的值
//	*m1 = m;
//	for (int i = 1; i <= n; i++)
//	{
//		if ((*T)[i].parent == 0 && i != *m1)
//		{
//			m = i;
//			break;
//		}
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		if ((*T)[i].parent == 0 && i != *m1 && (*T)[i].weight < (*T)[m].weight)
//		{
//			m = i;
//		}
//	}
//	//保存第二小的数
//	*m2 = m;
// 
// if(*m1>*m2)
// {
// int a=*m1;
// *m1=*m2;
// *m2=a;
// }
//}
//
///*创建哈夫曼编码*/
////从n个叶子结点到根节点逆向求解
//void CreateHuffmanCode(HuffmanTree* T, HuffmanCode* C, int n)
//{
//	//编码长度为s-1,第s位为\0
//	int s = n - 1;
//	//当前结点的父节点数组下标
//	int p = 0;
//	//为哈夫曼编码分配空间
//	C = (HuffmanCode*)malloc((n + 1) * sizeof(char*));
//	//临时保存当前叶子结点的哈夫曼编码
//	char* cd = (char*)malloc(n * sizeof(char));
//	//最后一位为\0
//	cd[n - 1] = '\0';
//
//	for (int i = 1; i <= n; i++)
//	{
//		s = n - 1;
//		//c指向当前结点,p指向此结点的父节点,两者交替上升，直到根节点
//		for (int c = i, p = (*T)[i].parent; p != 0; c = p, p = (*T)[p].parent)
//		{
//			//判断此结点为父节点的左孩子还是右孩子
//			if ((*T)[p].left == c)
//				cd[--s] = '0';//左孩子就是编码0
//			else
//				cd[--s] = '1';//右孩子就是编码1
//		}
//		//为第i个编码分配空间
//		C[i] = (char*)malloc((n - s) * sizeof(char));
//		//将此编码赋值到整体编码中
//		strcpy(C[i], &cd[s]);
//	}
//	//释放
//	free(cd);
//	//打印编码序列
//	for (int i = 1; i <= n; i++)
//	{
//		printf("%s",C[i]);
//		printf("\n");
//	}
//}
//
//int main()
//{
//	HuffmanTree T;
//	HuffmanCode C;
//	int n, w1, * w;
//	scanf_s("%d", &n);
//	w = (int*)malloc((n + 1) * sizeof(int));
//	for (int i = 1; i <= n; i++)
//	{
//		scanf_s("%d", &w1);
//		w[i] = w1;
//	}
//	printf("\n");
//	CreateHuffmanTree(&T, w, n);
//	CreateHuffmanCode(&T, &C, n);
//	return 0;
//}
//}
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
 typedef struct HTNode
{
	int left;
	int right;
	int parent;
	int weight;
}*HuffmanTree;
//typedef char* HuffmanCode;

int m;
//void minnum(int *min1,int *min2,HuffmanTree &T,int n,int a)
//{
//	for (int i = 1; i < n; i++)
//	{
//		if (T[i].parent==0&&T[a].weight > T[i].weight)
//		{
//			a = i;
//		}
//	}
//	*min1 = a;
//	for (int i = 1; i <n; i++)
//	{
//		if ((T)[i].parent == 0 && i != *min1)
//		{
//			a = i;
//			break;
//		}
//	}
//	for (int i = 1; i <n; i++)
//	{
//		if (i!=*min1&&T[i].parent == 0 && T[i].weight < T[a].weight)
//		{
//			a = i;
//		}
//	}
//	*min2 = a;
//	if (*min1 > *min2)
//	{
//		a = *min1; *min1 = *min2; *min2 = a;
//	}
//}
void minnum(int* min1, int* min2, HuffmanTree& T, int n)
{
	int a;//存储最小值的数组下标
   	for (int i = 1; i <= n; i++)
   	{
   		if (T[i].parent == 0)
   		{
   			a = i;
   			break;
   		}
   	}
	for (int i = 1; i < n; i++)
	{
		if (T[i].parent == 0 && T[a].weight > T[i].weight)
		{
			a = i;
		}
	}
	*min1 = a;
	for (int i = 1; i < n; i++)
	{
		if ((T)[i].parent == 0 && i != *min1)
		{
			a = i;
			break;
		}
	}
	for (int i = 1; i < n; i++)
	{
		if (i != *min1 && T[i].parent == 0 && T[i].weight < T[a].weight)
		{
			a = i;
		}
	}
	*min2 = a;
	if (*min1 > *min2)
	{
		a = *min1; *min1 = *min2; *min2 = a;
	}
}

void print(int to,int n,char **a)
{
	for (int i = to; i < n; i++)
	{
		printf("%c", (*a)[i]);
	}
	printf("\n");
}
void CreatHuffmanCode(HuffmanTree* T, char** Code, int n)
{
	int p;//父节点
	Code = (char**)malloc((n+1) * sizeof(char*));
	char* a =(char*) malloc((n)*sizeof(char));
	a[n-1] = '\0';
	for (int i = 1 ;i <=n; i++)
	{
		int to = n - 1;
		for (int j = i, p = (* T)[j].parent;p!=0&&p<m; j = p, p = (*T)[p].parent)
		{
			if (( * T)[p].left == j)
			{
				a[to]='0';
				to--;
			}
			else
			{
				a[to]='1';
				to--;
			}
		}
		print(to+1,n,&a);
	}
}
void creat(int n, HuffmanTree&T)
{
	for (int i = n + 1; i < m; i++)
	{
		int a1, a2;
		minnum(&a1, &a2, T, i);
		T[i].left = a1;
		T[i].right = a2;
		T[i].weight = T[a1].weight + T[a2].weight;
		T[a1].parent = T[a2].parent = i;
	}
}
int main()
{
	HuffmanTree T;
	char* c;
	int n=0;
	scanf("%d", &n);
	int wi;
	int* node =(int *) malloc((n+1) * sizeof(int));//节点数组
	for (int i = 1; i < n+1; i++)
	{
		scanf("%d", &wi);
		node[i] = wi;
	}

	int totalnode = 2 * n ;
	m = totalnode;
	T = (HTNode*)malloc(m * sizeof(HTNode));
	for (int i = 1; i < m; i++)
	{
		if (i <=n)
		{
			T[i].weight = node[i];
			T[i].parent = T[i].left = T[i].right = 0;;
		}	
		else
		{
			T[i].parent = T[i].left = T[i].right = 0;;
			T[i].weight = 0;
		}
	
	}
	creat(n, T);
//for(int i=n+1;i<m;i++)
//	{
//    int a1, a2;
//	minnum(&a1,&a2, T, i);
//	T[i].left = a1;
//	T[i].right = a2;
//	T[i].weight = T[a1].weight + T[a2].weight;
//	T[a1].parent = T[a2].parent = i;
//	}
CreatHuffmanCode(&T,&c ,n);
	return 0;
}

//}
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<string>
//#include<limits.h> //INT_MAX的头文件，不包含编译可能不会通过
//using namespace std;
//
//struct huffman_node {
//	int weight;//权值
//	int lchild, rchild;//左右子树
//	int parent;//父结点
//};
//
//
////************************************
//// Method:    select_tow_min 找出集合中两个最小的值
//// FullName:  select_tow_min
//// Access:    public 
//// Returns:   void
//// Qualifier:
//// Parameter: vector<huffman_node> & huffman_tree 存放哈夫曼树的集合
//// Parameter: int n 当前哈夫曼树共有多少结点
//// Parameter: int & first_min 第一个最小结点
//// Parameter: int & second_min 第二个最小结点
////************************************
//void select_tow_min(vector<huffman_node>& huffman_tree, int n, int& first_min, int& second_min)
//{
//	int min_value = INT_MAX;//一个很大的值
//	for (int i = 0; i < n; i++)//找出第一个最小结点
//	{
//		if (huffman_tree[i].parent == 0 && huffman_tree[i].weight < min_value)
//		{
//			min_value = huffman_tree[i].weight;
//			first_min = i;
//		}
//	}
//
//	min_value = INT_MAX;
//
//	for (int i = 0; i < n; i++)//找出第二个最小结点
//	{
//		if (huffman_tree[i].parent == 0 && huffman_tree[i].weight < min_value && i != first_min)
//		{
//			min_value = huffman_tree[i].weight;
//			second_min = i;
//		}
//	}
//	if (first_min > second_min)
//	{
//		swap(first_min, second_min);//保证编码唯一。因为给定题目是按照数字下标来区分左右子树的。
//	}
//}
//
////************************************
//// Method:    huffman_solve 求出哈夫曼编码
//// FullName:  huffman_solve
//// Access:    public 
//// Returns:   void
//// Qualifier:
//// Parameter: vector<huffman_node> & huffman_tree 存放哈夫曼树的结点
//// Parameter: vector<string> & code 存放哈夫曼编码
//// Parameter: vector<int> & weight 各个输入结点的权值
//// Parameter: int n 输入结点的总个数
////************************************
//void huffman_solve(vector<huffman_node>& huffman_tree, vector<string>& code, vector<int>& weight, int n) {
//	if (n <= 1)
//	{
//		return;
//	}
//	int m = n * 2 - 1;//哈夫曼树的所有结点数目
//	huffman_tree.resize(m);
//
//	//初始化
//	for (int i = 0; i < n; i++)
//	{
//		huffman_tree[i].weight = weight[i];
//		huffman_tree[i].parent = huffman_tree[i].lchild = huffman_tree[i].rchild = 0;
//	}
//	for (int i = n; i < m; i++)
//	{
//		huffman_tree[i].parent = huffman_tree[i].lchild = huffman_tree[i].rchild = 0;
//	}
//
//	//构造哈夫曼树
//	for (int i = n; i < m; i++)
//	{
//		int first_min, second_min;
//		select_tow_min(huffman_tree, i, first_min, second_min);//找出两个最小值
//		huffman_tree[i].lchild = first_min;//左子树
//		huffman_tree[i].rchild = second_min;//右子树
//		huffman_tree[first_min].parent = huffman_tree[second_min].parent = i;//父结点
//		huffman_tree[i].weight = huffman_tree[first_min].weight + huffman_tree[second_min].weight;//父结点的 weight
//	}
//
//	//求出每个叶节点的编码
//	for (int i = 0; i < n; i++) {
//		string str = "";
//		int child = i;//当前结点为孩子结点
//		int parent = huffman_tree[i].parent;//当前结点的父节点
//		do
//		{
//			if (huffman_tree[parent].lchild == child)
//			{
//				str = '0' + str;
//			}
//			else
//			{
//				str = '1' + str;
//			}
//			child = parent;
//			parent = huffman_tree[child].parent;
//		} while (parent != 0);//自底向上求出哈夫曼编码
//
//		code.push_back(str);
//	}
//}
//
//int main() {
//
//	int n;
//	cin >> n;
//	vector<int> v;
//	int data;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> data;
//		v.push_back(data);
//	}
//
//	vector<huffman_node> huffman_tree;//哈夫曼树的结点集合
//	vector<string> code;//哈夫曼编码
//
//	huffman_solve(huffman_tree, code, v, n);
//	for (vector<string>::iterator it = code.begin(); it != code.end(); it++) {
//		cout << (*it) << endl;
//	}
//	//system("pause");
//	return 0;
//}
